10820. Послать таблицу

 

Джимми вычисляет функцию Answer(x, y), где x, y Î {1, …, n} для некоторого n. Если известно значение Answer(x, y), то Джимми без труда вычислит Answer(k*x, k*y) для любого натурального k.

Например, если n = 4, то для того чтобы найти все возможные 16 значений Answer(x, y), Джимми изначально должен знать 11 значений: Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2), Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3), Answer(4, 1). Остальные значения могут быть получены простыми вычислениями: из Answer(1, 1) можно найти Answer(2, 2), Answer(3, 3), Answer(4, 4), из Answer(1, 2) можно найти Answer(2, 4), из Answer(2, 1) можно найти Answer(4, 2).

Функция Answer(x, y) не симметрична, то есть из Answer(x, y) нельзя найти Answer(y, x).

 

Вход. Содержит не более 600 строк. Каждая строка содержит натуральное число n, меньшее 50001. Последняя строка содержит 0 и не обрабатывается.

 

Выход. Для каждого n вывести минимальное количество значений Answer(x, y), которое Джимми должен знать, чтобы найти все n2 значений Answer(x, y).

 

Пример входа

2
5
0

 

Пример выхода

3
19

 

 

РЕШЕНИЕ

теория чисел - функция Эйлера

 

Анализ алгоритма

Обозначим через res(i) минимальное требуемое количество известных значений Answer(x, y), где x, y Î {1, …, i}. Очевидно, что res(1) = 1, так как при n = 1 достаточно знать Answer(1, 1). Пусть известно значение res(i). Для n = i + 1 следует найти значения Answer(1, i + 1), Answer(2, i + 1), … , Answer(i + 1, i + 1), Answer(i + 1, 1), Answer(i + 1, 2), … , Answer(i + 1, i). Значения Answer(j, i + 1) и Answer(i + 1, j), j Î {1, …, i + 1}, можно вычислить из известных значений, если НОД(j, i + 1) > 1, то есть если числа j и i + 1 не являются взаимно простыми. Следовательно, необходимо знать все такие Answer(j, i + 1) и Answer(i + 1, j), для которых j и i + 1 взаимно простые. Число таких значений равно 2 * j(i + 1), где j – функция Эйлера. Таким образом

res(1) = 1,

res(i + 1) = res(i) + 2 * j(i + 1), i > 1

 

Пример

Вычислим значения res(i) для некоторых начальных значений i:

res(1) = 1,

res(2) = res(1) + 2 * j(2) = 1 + 2 * 1 = 3,

res(3) = res(2) + 2 * j(3) = 3 + 2 * 2 = 7,

res(4) = res(3) + 2 * j(4) = 7 + 2 * 2 = 11

 

Реализация алгоритма

Массив f длины MAX = 50001 будет содержать значения j(n). В ячейках res[i] будет храниться минимальное требуемое количество известных значений Answer(x, y).

 

#define MAX 50001

int f[MAX], res[MAX];

 

Если n  = ,  то вычисление функции Эйлера j(n) совершаем по формуле

j(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... *  (1 - 1/pk),

где p1, p2, …, pk – простые множители числа n. Переменная i перебирает все значения от 2 до . Изначально положим result = n. Если i – простой делитель числа n, что вычисляем

result = result * ( 1 – 1/i) = result – result / i

 

int fi(int n)

{

  int i, result = n;

  for(i = 2 ; i <=  sqrt(1.0*n);i++)

  {

    if (n % i == 0) result -= result / i;

    while (n % i == 0) n /= i;

  }

  if (n > 1) result -= result / n;

  return result;

}

 

Основная часть программы. Находим все значения j(n), заносим их в массив f.

 

  f[1] = 0;

  for(i = 2; i < MAX; i++) f[i] = fi(i);

 

Полагаем res[1] = 1 и рекурсивно пересчитываем значения res[i].

 

  res[1] = 1;

  for(i = 2; i < MAX; i++) res[i] = res[i-1] + 2 * f[i];

 

Для каждого входного значения n выводим результат res[n].

 

  while(scanf("%d",&n),n)

    printf("%d\n",res[n]);